package linkedlist;

public class CopyListWithRandomPointer138 {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    // 方法1: 用HashMap
    // 方法2: 将原链表节点与新链表节点间隔用next串起来, 然后更新新节点的random指针, 最后将他们再串起来. 注意不能一边改random一边分离链表的方法有问题, 因为后面的节点可能指向前面, 所以必须分成两次遍历.
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Node oldCurr = head;
        while (oldCurr != null) {
            Node newCurr = new Node(oldCurr.val);
            newCurr.next = oldCurr.next;
            newCurr.random = oldCurr.random;

            Node oldNext = oldCurr.next;
            oldCurr.next = newCurr;
            oldCurr = oldNext;
        }

        Node newCurr = head.next;
        while (newCurr != null) {
            Node newNext = (newCurr.next != null) ? newCurr.next.next : null;
            newCurr.random = (newCurr.random != null) ? newCurr.random.next : null;
            newCurr = newNext;
        }

        oldCurr = head;
        Node oldPrev = null;
        Node newHead = head.next;
        Node newPrev = null;
        while (oldCurr != null) {
            newCurr = oldCurr.next;
            if (newPrev != null) {
                newPrev.next = newCurr;
            }
            newPrev = newCurr;

            Node oldNext = oldCurr.next.next;
            if (oldPrev != null) {
                oldPrev.next = oldCurr;
            }
            oldPrev = oldCurr;
            oldCurr = oldNext;
        }
        oldPrev.next = null;
        newPrev.next = null;
        return newHead;

        /* 这种一边改random一边分离链表的方法有问题, 因为后面的节点可能指向前面, 所以必须分成两次遍历.
        oldCurr = head;
        Node oldPrev = null;
        Node newHead = head.next;
        Node newPrev = null;
        while (oldCurr != null) {
            Node newCurr = oldCurr.next;
            newCurr.random = (newCurr.random != null) ? newCurr.random.next : null;
            if (newPrev != null) {
                newPrev.next = newCurr;
            }
            newPrev = newCurr;

            Node oldNext = oldCurr.next.next;
            if (oldPrev != null) {
                oldPrev.next = oldCurr;
            }

            oldPrev = oldCurr;
            oldCurr = oldNext;
        }
        oldPrev.next = null;
        newPrev.next = null;
        */
    }
}
